/*
 * cm_mib.c
 *
 *  Created on: 2014年9月23日
 *      Author: chens
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "cm_mib_id.h"
#include "cm_mib.h"

/*
 * @brief	删除并释放一个节点的空间
 */
void cmmib_delnode(struct cmmib_node **node)
{
	if (node == NULL || *node == NULL)
		return;
	if ((*node)->dptr != NULL)
		free((*node)->dptr);
	free(*node);
	*node = NULL;
}

/*
 * @brief	创建一个新的节点对象
 * @param	id: 节点的ID编号
 * @param	brief: 节点的描述字符串
 * @param	data: 节点中的数据
 * @param	len: 数据的长度
 * @return	成功返回一个非空的节点对象,失败返回NULL
 */
struct cmmib_node * cmmib_newnode(cmmib_id id, const char *brief,
		const void *data, unsigned len)
{
	struct cmmib_node * node = (struct cmmib_node *) calloc(1,
			sizeof(struct cmmib_node));

	if (node == NULL)
		return NULL;

	if (len <= sizeof(node->data)) {
		memcpy(&(node->data), data, len);
	} else {
		node->dptr = (char *) calloc(1, len);
		if (node->dptr == NULL) {
			free(node);
			return NULL;
		} else {
			memcpy(node->dptr, data, len);
		}
	}
	if (brief != NULL)
		strncpy(node->brief, brief, MIB_ALLOC_SIZE - 1);
	node->id = id;
	node->len = len;
	node->next = NULL;
	node->children = NULL;
	return node;
}

/*
 * @brief	更新ID相同两个节点的值，用节点nw替换节点od, parent是原指向od节点的父节点
 */
static inline void mib_replace(struct cmmib_node *od, struct cmmib_node *nw,
		struct cmmib_node *parent)
{
	if (parent != NULL)
		parent->children = nw;
	nw->children = od->children;
	nw->next = od->next;
}

/*
 * @brief	将root的儿子节点node放到其合适的位置, node必须是root的儿子
 */
static inline void insert_as_child(struct cmmib_node *node,
		struct cmmib_node *root)
{
	assert(cmmib_relation(node->id, root->id) == CMMIB_CHILD);
	struct cmmib_node *temp = root->children;
	if (temp == NULL) { // case 1: root's first child is NULL
		root->children = node;
		return;
	} else if (cmmib_cmp(node->id, temp->id) == 0) { // case 2: node == root's first child
		mib_replace(temp, node, root);
		cmmib_delnode(&temp);
		return;
	} else if (cmmib_cmp(node->id, temp->id) < 0) { // case 3: node should be root's first child
		root->children = node;
		node->next = temp;
		return;
	} else {
		/* case 4:  node should be inserted to somewhere, after root's first child */
		while (1) {
			if (temp->next == NULL) {
				temp->next = node;
				return;
			} else if (cmmib_cmp(node->id, temp->next->id) == 0) {
				mib_replace(temp->next, node, NULL);
				cmmib_delnode(&(temp->next));
				return;
			} else if (cmmib_cmp(node->id, temp->next->id) < 0) {
				node->next = temp->next;
				temp->next = node;
				return;
			}
			temp = temp->next;
		}
	}
}

/*
 * @brief	在root中遍历寻找ID等于 id 的节点
 */
struct cmmib_node * cmmib_find(cmmib_id id, struct cmmib_node *root)
{
	if (root == NULL || cmmib_cmp(id, root->id) < 0)
		return NULL;

	enum cmmib_relation rel = cmmib_relation(id, root->id);
	if (rel == CMMIB_HEIR || rel == CMMIB_CHILD) {
		return cmmib_find(id, root->children);
	} else if (rel == CMMIB_BROTHER) {
		/* 此处节点可能太多 不能用递归, 可能爆栈 */
		struct cmmib_node *temp = root->next;
		while (temp != NULL) {
			rel = cmmib_relation(id, temp->id);
			if (rel == CMMIB_HEIR || rel == CMMIB_CHILD) {
				return cmmib_find(id, temp->children);
			} else if (rel == CMMIB_SAME) {
				return temp;
			} else if (rel == CMMIB_BROTHER) {
				temp = temp->next;
			} else {
				return NULL;
			}
		}
		return NULL;
	} else if (rel == CMMIB_SAME) {
		return root;
	} else {
		return NULL;
	}
}

/*
 * @brief	在root中寻找node的父亲, 前提 node必须是root的后代
 */
static inline struct cmmib_node* find_parent(struct cmmib_node *node,
		struct cmmib_node *root)
{
	if (root == NULL || node == NULL || cmmib_cmp(node->id, root->id) < 0)
		return NULL;

	enum cmmib_relation rel = cmmib_relation(node->id, root->id);

	if (rel == CMMIB_HEIR) {
		return find_parent(node, root->children);
	} else if (rel == CMMIB_BROTHER) {
		/* 此处节点可能太多 不能用递归, 可能爆栈 */
		struct cmmib_node *temp = root->next;
		while (temp != NULL) {
			rel = cmmib_relation(node->id, temp->id);
			if (rel == CMMIB_HEIR)
				return find_parent(node, temp->children);
			else if (rel == CMMIB_CHILD)
				return temp;
			else if (rel == CMMIB_BROTHER)
				temp = temp->next;
			else
				return NULL;

		}
		return NULL;
	} else if (rel == CMMIB_CHILD) {
		return root;
	} else {
		return NULL;
	}
}

int cmmib_insert(struct cmmib_node *node, struct cmmib_node *root)
{
	enum cmmib_relation rel = cmmib_relation(node->id, root->id);
	switch (rel) {
	case CMMIB_CHILD:
	case CMMIB_HEIR: {
		struct cmmib_node *temp = find_parent(node, root);
		if (temp == NULL) {
			return -1;
		} else {
			insert_as_child(node, temp);
			return 0;
		}
	}
	case CMMIB_BROTHER:
	case CMMIB_ANCESTOR:
	case CMMIB_PARENT:
	case CMMIB_ERROR:
	case CMMIB_SAME:
		/* 这些关系都是不能插入的 */
		break;
	}
	return -1;
}

static inline void save_node(struct cmmib_node *node, void *arg)
{
	FILE *fp = (FILE *) arg;
	if (fwrite(node, sizeof(struct cmmib_node), 1, fp) <= 0) {
		// error return -1;
	}
	if (node->dptr != NULL) {
		if (fwrite(node->dptr, node->len, 1, fp) <= 0) {
			// error return -1;
		}
	}
}

/*
 * @brief	将以root为根的树保存到文件中,filename指明文件全路径名
 */
int save_tree(struct cmmib_node *root, const char *filename)
{
	if (root == NULL) {
		printf("ROOT not seted.\n");
		return -1;
	}

	FILE *fp = fopen(filename, "wb");
	if (fp == NULL) {
		printf("open mib.tree failed.\n");
		return -1;
	} else {
		for_each_node(root, save_node, fp);
	}
	fclose(fp);
	return 0;
}

/*
 * @brief	从文件中加载一颗mib树
 */
int load_tree(struct cmmib_node * root, const char *filename)
{
	if (root == NULL || filename == NULL)
		return -1;

	FILE *fp = fopen(filename, "rb");
	if (fp == NULL) {
		printf("open file(%s) failed.\n", filename);
		return -1;
	}

	struct cmmib_node *temp = root;
	while (1) {
		if (fread(temp, sizeof(struct cmmib_node), 1, fp) <= 0)
			break;
		temp->children = NULL;
		temp->next = NULL;
		if (temp->len > (int) sizeof(temp->data)) {
			temp->dptr = (char *) malloc(temp->len);
			if (temp->dptr == NULL)
				break;
			if (fread(temp->dptr, temp->len, 1, fp) <= 0)
				break;
		} else {
			temp->dptr = NULL;
		}
		cmmib_insert(temp, root);
		temp = cmmib_newnode(cmmib_error, NULL, NULL, 0);
	}
	if (temp != root)
		cmmib_delnode(&temp);

	return 0;
}
